package com.datastructure.monotonicstack;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Stack;

/**
 * @author: 临晖
 * @date: 2023/12/06
 * @description: 单调栈
 */


public class Solution {


    /**
     * 739. 每日温度
     * 提示
     * 中等
     * 1.7K
     * 相关企业
     * 给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
     * 示例 1:
     * 输入: temperatures = [73,74,75,71,69,72,76,73]
     * 输出: [1,1,4,2,1,1,0,0]
     * 示例 2:
     * 输入: temperatures = [30,40,50,60]
     * 输出: [1,1,1,0]
     * 示例 3:
     * 输入: temperatures = [30,60,90]
     * 输出: [1,1,0]
     *
     * @param temperatures
     * @return
     */
    public int[] dailyTemperatures(int[] temperatures) {
        Stack<Integer> stack = new Stack<>();
        int[] res = new int[temperatures.length];
        stack.push(0);
        for (int i = 1; i < temperatures.length; i++) {
            if (temperatures[i] > temperatures[stack.peek()]) {
                while (stack.size() != 0 && temperatures[i] > temperatures[stack.peek()]) {
                    res[stack.peek()] = i - stack.peek();
                    stack.pop();        //弹出
                }
                stack.push(i);
            } else {
                stack.push(i);
            }
        }

        return res;
    }


    /**
     * 496. 下一个更大元素 I
     * 简单
     * 1.1K
     * 相关企业
     * nums1 中数字 x 的 下一个更大元素 是指 x 在 nums2 中对应位置 右侧 的 第一个 比 x 大的元素。
     * 给你两个 没有重复元素 的数组 nums1 和 nums2 ，下标从 0 开始计数，其中nums1 是 nums2 的子集。
     * 对于每个 0 <= i < nums1.length ，找出满足 nums1[i] == nums2[j] 的下标 j ，并且在 nums2 确定 nums2[j] 的 下一个更大元素 。如果不存在下一个更大元素，那么本次查询的答案是 -1 。
     * 返回一个长度为 nums1.length 的数组 ans 作为答案，满足 ans[i] 是如上所述的 下一个更大元素 。
     * 示例 1：
     * <p>
     * 输入：nums1 = [4,1,2], nums2 = [1,3,4,2].
     * 输出：[-1,3,-1]
     * 解释：nums1 中每个值的下一个更大元素如下所述：
     * - 4 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
     * - 1 ，用加粗斜体标识，nums2 = [1,3,4,2]。下一个更大元素是 3 。
     * - 2 ，用加粗斜体标识，nums2 = [1,3,4,2]。不存在下一个更大元素，所以答案是 -1 。
     * 示例 2：
     * <p>
     * 输入：nums1 = [2,4], nums2 = [1,2,3,4].
     * 输出：[3,-1]
     * 解释：nums1 中每个值的下一个更大元素如下所述：
     * - 2 ，用加粗斜体标识，nums2 = [1,2,3,4]。下一个更大元素是 3 。
     * - 4 ，用加粗斜体标识，nums2 = [1,2,3,4]。不存在下一个更大元素，所以答案是 -1 。
     *
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        //Stack<Integer> stack = new Stack<>();
        //int[] ans = new int[nums1.length];
        //for (int i = 0; i < nums1.length; i++) {
        //    for (int j = 0; j < nums2.length; j++) {
        //        if (nums1[i] == nums2[j]) {
        //            stack.push(j);
        //            break;
        //        }
        //    }
        //}
        //int lastIndex = nums1.length - 1;
        //while (stack.size() != 0) {
        //    int temp = nums2[stack.peek()];
        //    boolean flag = false;
        //    for (int i = stack.peek() + 1; i < nums2.length; i++) {
        //        if (nums2[i] > temp) {
        //            flag = true;
        //            ans[lastIndex--] = nums2[i];
        //            break;
        //        }
        //    }
        //
        //    if (!flag) {
        //        ans[lastIndex--] = -1;
        //    }
        //    stack.pop();
        //}
        //
        //return ans;

        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums1.length; i++) {
            map.put(nums1[i], i);
        }

        int[] ans = new int[nums1.length];
        Arrays.fill(ans, -1);       //初始化

        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        for (int i = 1; i < nums2.length; i++) {
            if (nums2[i] <= nums2[stack.peek()]) {
                stack.push(i);
            } else {
                while (!stack.isEmpty() && nums2[i] > nums2[stack.peek()]) {
                    if (map.containsKey(nums2[stack.peek()])) {
                        Integer key = map.get(nums2[stack.peek()]);
                        ans[key] = nums2[i];
                    }
                    stack.pop();
                }

                stack.push(i);
            }
        }

        return ans;
    }


    /**
     * 503. 下一个更大元素 II
     * 中等
     * 892
     * 相关企业
     * 给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
     * 数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
     * 示例 1:
     * 输入: nums = [1,2,1]
     * 输出: [2,-1,2]
     * 解释: 第一个 1 的下一个更大的数是 2；
     * 数字 2 找不到下一个更大的数；
     * 第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
     * 示例 2:
     * 输入: nums = [1,2,3,4,3]
     * 输出: [2,3,4,-1,4]
     * 提示:
     * 1 <= nums.length <= 104
     * -109 <= nums[i] <= 109
     *
     * @param nums
     * @return
     */
    public int[] nextGreaterElements(int[] nums) {
        int[] ans = new int[2 * nums.length];
        int[] newNums = Arrays.copyOf(nums, 2 * nums.length);
        for (int i = 0; i < nums.length; i++) {
            newNums[i + nums.length] = nums[i];
        }
        Stack<Integer> stack = new Stack<>();
        stack.push(0);
        Arrays.fill(ans, -1);

        for (int i = 1; i < newNums.length; i++) {
            if (newNums[i] <= newNums[stack.peek()]) {
                stack.push(i);
            } else {            //大于
                while (!stack.isEmpty() && newNums[i] > newNums[stack.peek()]) {
                    ans[stack.peek()] = newNums[i];

                    stack.pop();
                }
                stack.push(i);
            }

        }

        return Arrays.copyOf(ans, nums.length);
    }


    /**
     * 42. 接雨水
     * 困难
     * 4.9K
     * 相关企业
     * 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
     * 示例 1：
     * 输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
     * 输出：6
     * 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
     * 示例 2：
     * 输入：height = [4,2,0,3,2,5]
     * 输出：9
     *
     * @param height
     * @return
     */
    public int trap(int[] height) {
        Stack<Integer> stack = new Stack<>();       //定义栈
        int res = 0;
        stack.push(0);


        for (int i = 1; i < height.length; i++) {
            int top = stack.peek();
            if (height[i] <= height[top]) {
                stack.push(i);
            } else {

                while (!stack.isEmpty() && height[i] > height[top]) {
                    int mid = stack.pop();      //中间数
                    if (!stack.isEmpty()) {
                        int left = stack.peek();        //左边
                        int w = Math.min(height[left], height[i]);
                        res += (w - height[mid]) * (i - left - 1);
                        top = stack.peek();
                    }
                }

                stack.push(i);

            }
        }
        return res;
    }


    /**
     * 84. 柱状图中最大的矩形
     * 困难
     * 2.6K
     * 相关企业
     * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
     * <p>
     * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
     * <p>
     * 示例 1:
     * <p>
     * 输入：heights = [2,1,5,6,2,3]
     * 输出：10
     * 解释：最大的矩形为图中红色区域，面积为 10
     * 示例 2：
     * <p>
     * 输入： heights = [2,4]
     * 输出： 4
     *
     * @param heights
     * @return
     */
    public int largestRectangleArea(int[] heights) {
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        // 数组扩容，在头和尾各加入一个元素
        int[] newHeights = new int[heights.length + 2];
        for (int index = 0; index < heights.length; index++) {
            newHeights[index + 1] = heights[index];
        }

        heights = newHeights;

        stack.push(0);
        for (int i = 1; i < heights.length; i++) {
            if (heights[i] >= heights[stack.peek()]) {
                stack.push(i);
            } else {
                while (!stack.isEmpty() && heights[i] < heights[stack.peek()]) {
                    int mid = stack.peek();
                    stack.pop();
                    int left = stack.peek();
                    int right = i;
                    int h = heights[mid];
                    int w = right - left - 1;
                    res = Math.max(res, w * h);
                }
                stack.push(i);
            }
        }

        return res;

    }


    public static void main(String[] args) {
        Solution so = new Solution();
        so.largestRectangleArea(new int[]{2, 1, 5, 6, 2, 3});
    }

}
